Large-scale key-value stores have become increasingly popular. A key-value store provides a simple get(key) and put(key,value) interface to the user. Providing strong consistency properties for these operations has become an increasingly important goal. However, the implementations of many key-value stores are proprietary and, as such, opaque to the users. Consequently, the users cannot reason about the implementations so as to be confident about their correctness. Instead, they can only test the system empirically, and analyze the test results (e.g., traces of operations) to see if the system is delivering the promised level of consistency. More useful consistency analysis can facilitate implementation of corrective actions (e.g., tuning the consistency level for future operations), and also provide a basis for proportional responses (e.g. compensation) to consistency violations.